package cn.edu.besti.cs1623.cw2324;

import ch16.ArrayIterator;
import ch16.ElementNotFoundException;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created by 春旺 on 2017/9/18.
 */
//********************************************************************
// Sorting.java Java Foundations
//
// Contains various sort algorithms that operate on an array of
// Comparable objects.
//********************************************************************
public class Sort
{
    //-----------------------------------------------------------------
// Sorts the specified array of integers using the selection
// sort algorithm.
//-----------------------------------------------------------------
    public static Comparable[] selectionSort (Comparable[] data)
    {
        int min;
        for (int index = 0; index < data.length-1; index++)
        {
            min = index;
            for (int scan = index+1; scan < data.length; scan++)
                if (data[scan].compareTo(data[min]) < 0)
                    min = scan;
            swap (data, min, index);
        }
        return data;
    }
    //-----------------------------------------------------------------
// Swaps two elements in the specified array.
//-----------------------------------------------------------------
    private static void swap (Comparable[] data, int index1, int index2)
    {
        Comparable temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
    //-----------------------------------------------------------------
// Sorts the specified array of objects using an insertion
// sort algorithm.
//-----------------------------------------------------------------
    public static void insertionSort (Comparable[] data)
    {
        for (int index = 1; index < data.length; index++)
        {
            Comparable key = data[index];
            int position = index;
// Shift larger values to the right
            while (position > 0 && data[position-1].compareTo(key) > 0)
            {
                data[position] = data[position-1];
                position--;
            }
            data[position] = key;
        }
    }
    //-----------------------------------------------------------------
// Sorts the specified array of objects using a bubble sort
// algorithm.
//-----------------------------------------------------------------
    public static void bubbleSort (Comparable[] data)
    {
        int position, scan;
        for (position = data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
                if (data[scan].compareTo(data[scan+1]) > 0)
                    swap (data, scan, scan+1);
        }
    }
    //-----------------------------------------------------------------
// Sorts the specified array of objects using the quick sort
// algorithm.
//-----------------------------------------------------------------
    public static void quickSort (Comparable[] data, int min, int max)
    {
        int pivot;
        if (min < max)
        {
            pivot = partition (data, min, max); // make partitions
            quickSort(data, min, pivot-1); // sort left partition
            quickSort(data, pivot+1, max); // sort right partition
        }
    }
    //-----------------------------------------------------------------
// Creates the partitions needed for quick sort.
//-----------------------------------------------------------------
    private static int partition (Comparable[] data, int min, int max)
    {
// Use first element as the partition value
        Comparable partitionValue = data[min];
        int left = min;
        int right = max;
        while (left < right)
        {
// Search for an element that is > the partition element
            while (data[left].compareTo(partitionValue) <= 0 && left < right)
                left++;
// Search for an element that is < the partitionelement
            while (data[right].compareTo(partitionValue) > 0)
                right--;
            if (left < right)
                swap(data, left, right);
        }
// Move the partition element to its final position
        swap (data, min, right);
        return right;
    }
    //-----------------------------------------------------------------
// Sorts the specified array of objects using the merge sort
// algorithm.
//-----------------------------------------------------------------
    public static void mergeSort (Comparable[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort (data, min, mid);
            mergeSort (data, mid+1, max);
            merge (data, min, mid, max);
        }
    }
    //-----------------------------------------------------------------
// Sorts the specified array of objects using the merge sort
// algorithm.
//-----------------------------------------------------------------
    public static void merge (Comparable[] data, int first, int mid,
                              int last)
    {
        Comparable[] temp = new Comparable[data.length];
        int first1 = first, last1 = mid; // endpoints of first subarray
        int first2 = mid+1, last2 = last; // endpoints of second subarray
        int index = first1; // next index open in temp array
// Copy smaller item from each subarray into temp until one
// of the subarrays is exhausted
        while (first1 <= last1 && first2 <= last2)
        {
            if (data[first1].compareTo(data[first2]) < 0)
            {
                temp[index] = data[first1];
                first1++;
            }
            else
            {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }
        // Copy remaining elements from first subarray, if any
        while (first1 <= last1)
        {
            temp[index] = data[first1];
            first1++;
            index++;
        }
// Copy remaining elements from second subarray, if any
        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
        }
// Copy merged data into original array
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }
    /*
    * 堆排序
    */
    public static void HeapSort(int []H,int N)
    {
        int i,temp;
        for(i=N/2;i>=0;--i)
        {
            MaxHeap(H,i,N);  //建立最大堆，找出了最大元素
        }
        for(i=N-1;i>=0;--i)
        {
            temp=H[0];
            H[0]=H[i];
            H[i]=temp;  //互换，最大值给数组最后元素
            MaxHeap(H,0,i-1);
        }
    }
    public static void MaxHeap(int []H,int n,int N){//建立最大堆
        int l=2*n+1;  //数组从0开始（l=2*n+1,r=2*(n+1)）和从1开始(l=2*n,r=2*n+1)的左右孩子标志不一样
        int r=2*n+2;
        int max; //l,r,max均表示数组坐标
        int temp;//表示元素，交换时候用
        if (l<N&&H[l]>H[n])  	max=l; //左节点大
        else	max=n;  //根大
        if(r<N&&H[r]>H[max])  max=r; //右节点大
        if(max!=n) //交换
        {
            temp=H[n];
            H[n]=H[max];
            H[max]=temp;
            MaxHeap(H,max,N);//保证最大堆
        }
    }
/*
* 桶排序
* */


    public static int[] bucketSort(int[] nums, int maxNum){
        int[] sorted = new int[maxNum+1];

        for(int i=0; i<nums.length; i++){
            sorted[nums[i]] = nums[i];//把数据放到对应索引的位置
        }
        int b = 0;
        for(int i = 0;i < sorted.length;i ++){

                if (sorted[i] != 0){
                    nums [b] = sorted[i];
                    b++;
                }
        }
        return nums;
    }


    /*
    * 二叉树排序
    */
    public static void BinaryTreeSort(Comparable []data) throws ElementNotFoundException {
        LinkedBinarySearchTree tree = new LinkedBinarySearchTree();//创建树
        //将元素加到树中
        for (int i = 0;i < data.length;i++){
            tree.add(data[i]);
        }
        ArrayList iter = (ArrayList) tree.preorder();// 获取他的中序遍历的结果
        for (int i = 0;i< data.length; i++){
            data[i] = (Comparable) iter.get(i);
        }

        }
    /*
    * 希尔排序
    */
    public static void shellSort(int[] data){
        if(data == null || data.length <= 1){
            return;
        }
        int inNum = data.length/2;
        while(inNum >=1){
            for(int i=0;i<data.length;i++){
                for(int j=i;j<data.length-inNum;j=j+inNum){
                    if(data[j]>data[j+inNum]){
                        int tem = data[j];
                        data[j] = data[j+inNum];
                        data[j+inNum] = tem;
                    }
                }
            }
            inNum = inNum/2;
        }
    }
}